package com.algorithm.quick;/*
 *@Author:DOWN
 *@Date:2022/1/20 15:09
 *@Comment:输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

           示例 1：
           输入：arr = [3,2,1], k = 2
           输出：[1,2] 或者 [2,1]

           示例 2：
           输入：arr = [0,1,2,1], k = 1
           输出：[0]
 */

import java.util.Arrays;
import java.util.Random;

public class Solution40 {
    private static Random random = new Random();
    private static int[] results={};

    public static int[] getLeastNumbers(int[] nums, int k) {
        if(nums.length==0&&k>0){
            return results;
        }
        sortTwoWays(nums, 0, nums.length - 1, k,0);
        return results;
    }

    public static void sortTwoWays(int[] arrs, int l, int r, int k,int denth) {
        if(r<0){
            return;
        }
        int changeIndex = l + (random).nextInt(r - l + 1);
        swap(arrs, l, changeIndex);
        int i = l + 1, j = r;
        while (true) {
            while (i <= j && arrs[i] < arrs[l]) {
                i++;
            }
            while (j >= i && arrs[j] > arrs[l]) {
                j--;
            }
            if (i >= j) {
                break;
            }
            swap(arrs, i, j);
            i++;
            j--;
        }
        swap(arrs, l, j);
        if(j==k-1&&j>-1){
            results=Arrays.copyOf(arrs,j+1);
            return;
        }else if(l>=r){
            return;
        } if(j<k-1){
            //[j+1,arrs.length]
            sortTwoWays(arrs, j+1, r, k,denth+1);
        }else {
            //[0,j-1]
            sortTwoWays(arrs, l, j-1, k,denth+1);
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
    public static void main(String[] args){
        int[] ints={1,2,3};
        System.out.println(Arrays.toString(getLeastNumbers(ints,0)));
        System.out.println(Arrays.toString(ints));
    }
}
